#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;


int maxSubsetSum(const vector<int> &arr) {
  if (arr.empty()) {
    return 0;
  }

  if (arr.size() == 1) {
    return arr[0];
  }

  vector<int> results(arr.size(), 0);

  results[0] = arr[0];
  results[1] = max(arr[0], arr[1]);

  for (int i = 2; i < arr.size(); ++i) {
    int candidate1 = arr[i] + results[i - 2];
    int candidate2 = arr[i];
    int candidate3 = results[i - 1];

    results[i] = max({candidate1, candidate2, candidate3});
  }

  return results.back();
}

vector<int> maxSubsetElements(const vector<int> &arr) {
  if (arr.empty() || arr.size() == 1) {
    return arr;
  }

  vector<vector<int>> results;     // 保存相加的元素
  vector<int> sums(arr.size(), 0); // 保存最大不相邻和

  sums[0] = arr[0];
  results.push_back({arr[0]});

  int candidate = max(arr[0], arr[1]);  
  sums[1] = candidate;
  results.push_back({candidate});

  for (int i = 2; i < arr.size(); ++i) {
    int candidate1 = arr[i] + sums[i - 2];
    int candidate2 = sums[i - 1];
    int candidate3 = arr[i];

    int maxCandidate = max({candidate1, candidate2, candidate3});
    sums[i] = maxCandidate;
    
    if (maxCandidate == candidate3) {  
      results.clear();
      results.push_back({candidate3});
    }
    else if (maxCandidate == candidate2) {
      results.push_back(results[i - 1]);
    }
    else {
      // maxCandaite1
      vector<int> tmp = results[i - 2];
      tmp.push_back(arr[i]);
      results.push_back(tmp);
    }
  }

  return results.back();
}

int main(int argc, char const *argv[])
{
  /* code */
  maxSubsetSum({75, 105, 120, 75, 90, 135});
  return 0;
}
